import java.util.*;

public class ch5_06_primes {
  int _sieve_size;
  boolean[] bs;   // 10^7 should be enough for most cases
  List<Integer> primes = new ArrayList<Integer>();   // compact list of primes in form of vector<int>

  // first part

  void sieve(int upperbound) {          // create list of primes in [0..upperbound]
    _sieve_size = upperbound + 1;                   // add 1 to include upperbound
    bs = new boolean[_sieve_size];
    Arrays.fill(bs,true);                                    // set all bits to 1
    bs[0] = bs[1] = false;                                     // except index 0 and 1
    for (long i = 2; i < _sieve_size; i++) if (bs[(int)i]) {
      // cross out multiples of i starting from i * i!
      for (long j = i * i; j < _sieve_size; j += i) bs[(int)j] = false;
      primes.add((int)i);  // also add this vector containing list of primes
  } }                                           // call this method in main method

  boolean isPrime(long N) {                 // a good enough deterministic prime tester
    if (N < _sieve_size) return bs[(int)N];                   // O(1) for small primes
    for (int i = 0; i < primes.size(); i++)
      if (N % primes.get(i) == 0) return false;
    return true;                    // it takes longer time if N is a large prime!
  }                      // note: only work for N <= (last prime in vi "primes")^2


  // second part

  List<Integer> primeFactors(long N) {   // remember: vi is vector of integers, long is long long
    List<Integer> factors = new ArrayList<Integer>();  // vi `primes' (generated by sieve) is optional
    int PF_idx = 0;
    long PF = primes.get(PF_idx);     // using PF = 2, 3, 4, ..., is also ok
    while (N != 1 && (PF * PF <= N)) {   // stop at sqrt(N), but N can get smaller
      while (N % PF == 0) { N /= PF; factors.add((int)PF); }    // remove this PF
      PF = primes.get(++PF_idx);                              // only consider primes!
    }
    if (N != 1) factors.add((int)N);     // special case if N is actually a prime
    return factors;         // if pf exceeds 32-bit integer, you have to change vi
  }

  // third part

  long numPF(long N) {
    int PF_idx = 0;
    long PF = primes.get(PF_idx), ans = 0;
    while (N != 1 && (PF * PF <= N)) {
      while (N % PF == 0) { N /= PF; ans++; }
      PF = primes.get(++PF_idx);
    }
    if (N != 1) ans++;
    return ans;
  }

  long numDiffPF(long N) {
    int PF_idx = 0;
    long PF = primes.get(PF_idx), ans = 0;
    while (N != 1 && (PF * PF <= N)) {
      if (N % PF == 0) ans++;                           // count this pf only once
      while (N % PF == 0) N /= PF;
      PF = primes.get(++PF_idx);
    }
    if (N != 1) ans++;
    return ans;
  }

  long sumPF(long N) {
    int PF_idx = 0;
    long PF = primes.get(PF_idx), ans = 0;
    while (N != 1 && (PF * PF <= N)) {
      while (N % PF == 0) { N /= PF; ans += PF; }
      PF = primes.get(++PF_idx);
    }
    if (N != 1) ans += N;
    return ans;
  }

  long numDiv(long N) {
    int PF_idx = 0;
    long PF = primes.get(PF_idx), ans = 1;             // start from ans = 1
    while (N != 1 && (PF * PF <= N)) {
      long power = 0;                                             // count the power
      while (N % PF == 0) { N /= PF; power++; }
      ans *= (power + 1);                              // according to the formula
      PF = primes.get(++PF_idx);
    }
    if (N != 1) ans *= 2;             // (last factor has pow = 1, we add 1 to it)
    return ans;
  }

  long sumDiv(long N) {
    int PF_idx = 0;
    long PF = primes.get(PF_idx), ans = 1;             // start from ans = 1
    while (N != 1 && (PF * PF <= N)) {
      long power = 0;
      while (N % PF == 0) { N /= PF; power++; }
      ans *= ((long)Math.pow((double)PF, power + 1.0) - 1) / (PF - 1);         // formula
      PF = primes.get(++PF_idx);
    }
    if (N != 1) ans *= ((long)Math.pow((double)N, 2.0) - 1) / (N - 1);        // last one
    return ans;
  }

  long EulerPhi(long N) {
    int PF_idx = 0;
    long PF = primes.get(PF_idx), ans = N;             // start from ans = N
    while (N != 1 && (PF * PF <= N)) {
      if (N % PF == 0) ans -= ans / PF;                // only count unique factor
      while (N % PF == 0) N /= PF;
      PF = primes.get(++PF_idx);
    }
    if (N != 1) ans -= ans / N;                                     // last factor
    return ans;
  }

  void run(){
    // first part: the Sieve of Eratosthenes
    sieve(10000000);                       // can go up to 10^7 (need few seconds)
    System.out.printf("%b\n", isPrime(2147483647));                        // 10-digits prime
    System.out.printf("%b\n", isPrime(136117223861L));        // not a prime, 104729*1299709

    // second part: prime factors
    List<Integer> res = primeFactors(2147483647);   // slowest, 2147483647 is a prime
    for (int i : res) System.out.printf("> %d\n", i);

    res = primeFactors(136117223861L);   // slow, 2 large pfactors 104729*1299709
    for (int i : res) System.out.printf("# %d\n", i);

    res = primeFactors(142391208960L);   // faster, 2^10*3^4*5*7^4*11*13
    for (int i : res) System.out.printf("! %d\n", i);

    //res = primeFactors((long)(1010189899 * 1010189899)); // "error"
    //for (vi::iterator i = res.begin(); i != res.end(); i++) System.out.printf("^ %d\n", *i);

    // third part: prime factors variants
    System.out.printf("numPF(%d) = %d\n", 50, numPF(50)); // 2^1 * 5^2 => 3
    System.out.printf("numDiffPF(%d) = %d\n", 50, numDiffPF(50)); // 2^1 * 5^2 => 2
    System.out.printf("sumPF(%d) = %d\n", 50, sumPF(50)); // 2^1 * 5^2 => 2 + 5 + 5 = 12
    System.out.printf("numDiv(%d) = %d\n", 50, numDiv(50)); // 1, 2, 5, 10, 25, 50, 6 divisors
    System.out.printf("sumDiv(%d) = %d\n", 50, sumDiv(50)); // 1 + 2 + 5 + 10 + 25 + 50 = 93
    System.out.printf("EulerPhi(%d) = %d\n", 50, EulerPhi(50)); // 20 integers < 50 are relatively prime with 50
  }

  public static void main(String[] args){
    new ch5_06_primes().run();
  }
}
